package com.shuang.dp19;

import java.util.HashSet;
import java.util.List;

//class Solution {
//    //转为完全背包问题
//    //字符串作为背包 数组中单词作为物品 在数组中 选择单词看看是否能装满字符串 即组成字符串
//    public boolean wordBreak(String s, List<String> wordDict) {
//        //dp[i] 表示 长度为i的字符串 能被字典中单词组成时 dp[i]为true
//        boolean[] dp = new boolean[s.length() + 1];
//
//        //递推公式
//        //当dp[j]为true时（字符串长度前j个能组成） 且字符串的 [j,i）区间的子串也在字典单词中时 dp[i]为true
//
//        //初始化
//        dp[0] = true; //没有特定意义 只是保证程序递推公式能进行 题目字符串长度也是大于等于1的 其余初始化都为false判断完能组成才会赋值为true
//
//        //将字典中字符放进Set集合
//        HashSet<String> set = new HashSet<>(wordDict);
//
//        //遍历顺序 这是排列问题 因为要保证单词顺序才能组成字符串 所以先背包后物品
//        for (int i = 1; i <= s.length(); i++) {
//            for (int j = 0; j < i && !dp[i]; j++) {
//                if (set.contains(s.substring(j, i)) && dp[j]) {
//                    dp[i] = true;
//                }
//            }
//        }
//
//        return dp[s.length()];
//    }
//}

//方法二:
class Solution {
    //转为完全背包问题
    //字符串作为背包 数组中单词作为物品 在数组中 选择单词看看是否能装满字符串 即组成字符串
    public boolean wordBreak(String s, List<String> wordDict) {
        //dp[i] 表示 长度为i的字符串 能被字典中单词组成时 dp[i]为true
        boolean[] dp = new boolean[s.length() + 1];

        //递推公式
        //当dp[j]为true时（字符串长度前j个能组成） 且字符串的 [j,i）区间的子串也在字典单词中时 dp[i]为true

        //初始化
        dp[0] = true; //没有特定意义 只是保证程序递推公式能进行 题目字符串长度也是大于等于1的 其余初始化都为false判断完能组成才会赋值为true

        //遍历顺序 这是排列问题 因为要保证单词顺序才能组成字符串 所以先背包后物品
        for (int i = 1; i <= s.length(); i++) {
            for (String word : wordDict) {
                //拿到字典中的每个单词的长度
                int len = word.length();

                //当达到一个字符子串长度 并且符合字典中拿到的单词时
                if (i >= len && dp[i - len] && word.equals(s.substring(i - len, i))) {
                    dp[i] = true;
                    //找到一个单词符合 跳过内层循环
                    break;
                }
            }
        }

        return dp[s.length()];
    }
}